The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
Border Gateway Protocol (BGP) is a path vector routing protocol for exchanging routing information among network elements in the same or different Autonomous System (AS). The function of a BGP-enabled network element (a BGP host or peer) is to exchange network reachability information with other BGP-enabled network elements. The most commonly implemented version of BGP is BGP-4, which is defined in RFC1771 (published by the Internet Engineering Task Force (IETF) in March 1995).
To exchange routing information, two BGP hosts first establish a BGP peering session by exchanging BGP OPEN messages. The BGP hosts then exchange their full routing tables. After this initial exchange, each BGP host sends to its BGP peer or peers only incremental updates for new, modified, and unavailable or withdrawn routes in one or more BGP UPDATE messages. A route is a unit of information that pairs a network destination with the attributes of a network path to that destination. Examples of path attributes include, but are not limited to, the ORIGIN attribute (which indicates how a BGP peer learned about a route), the AS_PATH attribute (which indicates the Autonomous Systems through which a route passes), the NEXT_HOP attribute (which is the address of the border router that is the next hop in a route), and the LOCAL_PREF attribute (which indicates the BGP peer's degree of preference of an exit point from the local AS for a route). In BGP literature, routes are sometimes termed prefixes.
When a BGP host receives routes, the host determines a best path to each reachable node, for example, by computing a shortest path first (SPF) spanning tree of nodes between the host and the reachable node. In certain cases, other computations and route resolution steps are performed. Fully resolved routes are stored in a forwarding information base (FIB) that is coupled to or hosted in line cards of the BGP host. In this architecture, packet-forwarding logic in the line cards can determine a next hop for a received packed by performing a lookup in the FIB.
For example, in Multiprotocol Label Switching virtual private networks (MPLS VPNs), Multi-Protocol BGP (MP-BGP) provides the framework to exchange reachability information about many protocols such as IPv4, VPNv4, IPv6, multicast, and others. MP-BGP allocates labels for VPN prefixes in an advertising provider edge router (denoted PE1 herein) and accepts them in a receiving provider router (PE2).
An MPLS VPN network logically comprises a control plane (analogous to call setup) and a forwarding plane (analogous to call transmission). As a specific example, assume that a sending customer edge router (CE1) advertises an IP prefix, “5.5.5.5/32,” to PE1 via a routing protocol such as BGP, Enhanced Interior Gateway Routing Protocol (EIGRP), Router Information Protocol (RIP), or the like.
After receiving the advertisement, PE1 converts the IP prefix 5.5.5.5/32 into a VPN prefix, “1:1:5.5.5.5/32.” Next, PE1 allocates the label (for example, 20) to 1:1:5.5.5.5./32 and installs it in both BGP and the Label Forwarding Information Base (LFIB). PE1 then advertises the prefix to PE2 via MP-BGP. PE routers, which use an Interior Gateway Protocol (IGP) such as Intermediate System-to-Intermediate System (IS-IS) or Open Shortest Path First (OSPF), do not have any VPN knowledge. PE routers might optionally exchange IPv4 routes via MP-BGP.
PE2, after receiving the MP-BGP advertisement, checks whether the VPN prefix is acceptable by comparing the route target (RT) values. If acceptable, PE2 installs the prefix and label in the BGP and VPN Routing and Forwarding (VRF) FIB tables and advertises the prefix to CE2. In the meantime, the FIB performs a recursion resolution process to find a valid route and label to VPN prefix's next-hop (for example, PE1). If the FIB finds a valid route, the FIB installs the next-hop label in the label stack that also contains the VPN label. This label stack is what FIB (at PE2) will use to forward VPN packets toward PE1.
In current practice, some routers do not support a hierarchical FIB structure, but FIB entries may have parent FIB entries that are associated with dependent (child) FIB entries. An example of a parent FIB entry is an IGP entry for a BGP next hop; an example of a dependent FIB entry is a BGP route entry. In this arrangement, each dependent FIB entry contains its own forwarding information. When a change occurs in a parent FIB entry, all the dependent entries are queued for re-performing the recursion resolution process. During re-resolution, affected routes are not routable; as a result, connectivity is lost for some BGP-destined data streams. Some routers are known to have this problem.
One approach for addressing this problem is to create a hierarchical FIB in which dependent FIB entries are linked directly to the forwarding information of the parent entry. This ensures that the dependent entries immediately leverage any update to the forwarding information of the parent. However, not all routers can support such linked FIB entries. There is a need to avoid the loss of connectivity and other disadvantages of current practice without requiring a linked hierarchical structure.